package com.lft.ten_commonly_used_algorithms02.divide_and_conquer;

/**
 * 分治算法——解决汉诺塔问题
 */
public class DivideAndConquerAlgorithm {
	public static void main(String[] args) {
		char a = 'A';
		char b = 'B';
		char c = 'C';
		hanoiTower(5, a, b, c);
	}
	
	public static void hanoiTower(int num, char a, char b, char c) {
		// 如果是有 n = 1 个盘， A->C
		if (num == 1) {
			System.out.println("第 1 个盘：" + a + " -> " + c);
		} else {
			// 如果是有 n >= 2 个盘，我们总是可以看做是两个盘 1. 最下边的盘 2.上面的盘。
			// 1. 先把上面的所有盘 A -> B，借助C
			hanoiTower(num - 1, a, c, b);
			// 2. 再把最下面盘 A -> C，借助B
			System.out.println("第 " + num + " 个盘：" + a + " -> " + c);
			// 3. 再把B上面的盘 B -> C，借助A
			hanoiTower(num - 1, b, a, c);
		}
	}
}
